/*************************************************************************
	> File Name: Leetcode_04.cpp
	> Author: 
	> Mail: 
	> Created Time: Tue 13 Aug 2024 08:30:21 PM CST
	
	给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。

	算法的时间复杂度应该为 O(log (m+n)) 。
 ************************************************************************/

#include<iostream>
#include <vector>
using namespace std;


int findK(vector<int>& nums1, int p1, vector<int>& nums2, int p2, int k) {
	int n1 = nums1.size(), n2 = nums2.size();
	if(p1 == n1) return nums2[k - 1];
	if(p2 == n2) return nums1[k - 1];
	if(k == 1) return min(nums1[p1], nums2[p2]);
	int cnt1 = min(k / 2, n1 - p1);
	int cnt2 = min(k - cnt1, n2 - p2);
	cnt1 = k - cnt2;
	if(nums1[p1 + cnt1 - 1] <= nums2[p2 + cnt2 - 1]) 
		return findK(nums1, p1 + cnt1, nums2, p2, k - cnt1);
	else
		return findK(nums1, p1, nums2, p2 + cnt2, k - cnt2);
}

double findMedianSortedArray(vector<int>& nums1, vector<int>& nums2) {
	int n1 = nums1.size(), n2 = nums2.size();
	double a = findK(nums1, 0, nums2, 0, (n1 + n2) / 2);
	double b = findK(nums1, 0, nums2, 0, (n1 + n2) / 2 + 1);
	return (n1 + n2) % 2 ? b : (a + b) / 2.0; 
}

int main() {
	vector<int> nums1 {1, 3};
	vector<int> nums2 {2};
	cout << findMedianSortedArray(nums1, nums2) << endl;
	return 0;
}